from typing import List


class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m = len(heights)
        n = len(heights[0])
        def f(cost):
            visited = set()
            def dfs(x,y):
                if x < 0 or x >= m: return
                if y < 0 or y >= n: return
                for nx, ny in [(x-1,y),(x+1,y),(x,y+1),(x,y-1)]:
                    if (nx, ny) in visited: continue
                    if nx < 0 or nx >= m: continue
                    if ny < 0 or ny >= n: continue
                    if abs(heights[nx][ny] - heights[x][y]) > cost: continue
                    visited.add((nx, ny))
                    dfs(nx,ny)
            dfs(0,0)
            return (m-1, n-1) in visited

        l = 0
        r = int(1e6+1)
        while l <= r:
            mid = (l  + r) >> 1
            if f(mid):
                r = mid - 1
            else:
                l = mid + 1
        return r + 1

if __name__ == '__main__':
    s = Solution()
    r = s.minimumEffortPath([[1,2,2],[3,8,2],[5,3,5]])
    print(r)